package gee

import "strings"

/*
	其实这种url结构的最好是用radix tree， 也就是优化的trie
	但是我不会捏

	这个trie的逻辑我是这么认为的：
	: 代表任意一个word
	* 代表任意一个到任意多个word
	ps: 其他的我不是很会写（

	关于我为什么认为 :, *, name这三个是冲突的呢
	假设这是不冲突的，你现在插入 /:/hi, /* /hi, /hi/hi
	那么这三条应该是三条不同的记录吧，
		root
		/ | \
       :  *  /hi
      /   |    \
     /hi  /hi  /hi

	那么我现在插入/hi/hello, 应该插在这三条路的哪一条呢？显然conflict了

	有bug可以及时告诉我！我现在还没觉得有什么问题


 	update: 我现在知道*filepath的作用了，是为了给*命名，方便后面去找匹配上的地方是哪里
			:name同理, 所以现在加点东西

*/

type node struct {
	pattern  string  // 整个url
	part     string  // 部分url
	children []*node //表示子节点数组
	state    int8    //表示这个节点 0: 没子节点 1: 子节点里没通配符 2: 子节点是通配符
}

func (u *node) DFS() {
	if u.children == nil {
		return
	}
	for _, child := range u.children {
		println(child.part)
		child.DFS()
	}
}

// 封装一下，避免对用户暴露过多的参数，depth对于用户来说是没有必要的

func (u *node) insert(pattern string) bool {
	insertRes := u._insert(pattern, splitURL(pattern), 0)
	return insertRes
}

func (u *node) search(pattern string) (*node, bool) {
	return u._search(splitURL(pattern), 0)
}

func splitURL(url string) []string {

	return strings.Split(url, "/")
}

func (u *node) _insert(pattern string, parts []string, depth int) bool {
	if len(parts) == depth { // 这里代表是匹配到parts数组最后了
		if u.pattern != "" { // 如果这个地方已经有url覆盖了，说明url冲突了，应该要报错
			return false
		}
		u.pattern = pattern
		return true
	}

	// 当前part的名字
	currentPartName := parts[depth]

	if u.state == 0 { // 没有子节点
		// 给切片分配地址
		u.children = make([]*node, 0)

		if currentPartName != "" && (currentPartName[0] == '*' || currentPartName[0] == ':') { // 状态码改为 2
			u.state = 2
		} else { // 状态码改为 1
			u.state = 1
		}
		// new 一个子节点
		newChild := new(node)
		newChild.part = currentPartName

		// 子节点加入子节点数组
		u.children = append(u.children, newChild)
		return newChild._insert(pattern, parts, depth+1)

	} else if u.state == 1 { // 子节点不是通配符
		//出现矛盾
		if currentPartName != "" && (currentPartName[0] == '*' || currentPartName[0] == ':') {
			return false
		}

		// 分为两种
		// 第一种子节点里这个part出现过了
		for _, child := range u.children {
			if child.part == currentPartName {
				return child._insert(pattern, parts, depth+1)
			}
		}
		// 第二种 子节点里没出现过
		// new 一个子节点
		newChild := new(node)
		newChild.part = currentPartName

		// 子节点加入子节点数组
		u.children = append(u.children, newChild)
		return newChild._insert(pattern, parts, depth+1)
	} else { // 子节点为通配符
		if currentPartName != u.children[0].part { // * 与 :也会矛盾
			return false
		}
		//下一个节点
		return u.children[0]._insert(pattern, parts, depth+1)
	}
}

func (u *node) _search(parts []string, depth int) (*node, bool) {
	// 匹配到最后+1了，说明完全匹配上了
	if depth == len(parts) {
		return u, u.pattern != ""
	}

	// parts没匹配完，发现trie已经无能匹配上的节点了，说明无法handle
	if u.children == nil {
		return nil, false
	} else {
		// 要么是 : , 要么是name , 要么是 *

		// : 与 name 可以归纳为一种
		for _, child := range u.children {
			if child.part == parts[depth] || (child.part != "" && child.part[0] == ':') {
				return child._search(parts, depth+1)
			}
		}
		// * 要么是1
		if res, ok := u.children[0]._search(parts, depth+1); ok {
			return res, ok
		}
		// 要么是n
		if res, ok := u._search(parts, depth+1); ok {
			return res, ok
		}
		return nil, false
	}
}

func TrieTest() {
	trie := new(node)

	var str = "/hi/hello"

	str = "/hi/*"
	if ok := trie.insert(str); !ok {
		println("URL conflict")
	}
	//trie.DFS()

	str = "/hello/hi"
	if ok := trie.insert(str); !ok {
		println("URL conflict")
	}
	//trie.DFS()

	str = "/halo/:/hi"
	if ok := trie.insert(str); !ok {
		println("URL conflict")
	}

	res, ok := trie.search("/hi/hello/hi/hello/hi")
	println(res, ok)

	res, ok = trie.search("/halo/hi/hi/hi")
	println(res, ok)

	res, ok = trie.search("/hi/hi/hi")
	println(res, ok)
}
